package com.arrays.a2;

import java.util.Arrays;

public class SearchInsert {
    //二分搜索出现的数
    public static int searchInsert(int[] nums, int target) {
        int l=0;
        int r=nums.length-1;
        while (l<=r){
            int mid=(l+r)/2;
            if (nums[mid]==target){
                return mid;
            }else if (nums[mid]>target){
                r=mid-1;
            }else {
                l=mid+1;
            }
        }
//        return target<=nums[l]?l:l+1;
        return l;
    }

    //搜索第一次出现和最后一次出现的数字
    public static int[] searchRange(int[] nums, int target) {
        if (nums.length==0){
            return new int[]{-1,-1};
        }
        int l=0;
        int r=nums.length-1;
        //第一次出现
        while (l<r) {
            int mid = (l + r) / 2;
            if (nums[mid] >= target) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
            if (nums[r]!=target) {
                return new int[]{-1, -1};
            }
            int L=r;
            l=0;
            r=nums.length-1;
            //最后一次出现
        while (l<r){
            int mid=(l+r+1)/2;
            if (nums[mid]<=target){
                l=mid;
            }else {
                r=mid-1;
                }
            }
            return new int[]{L,r};

    }

    public static void main(String[] args) {
        int[] a={1,5,5,6,5,5};
        int res = searchInsert(a, 5);
        int[] res2 = searchRange(a, 5);
        System.out.println(res);
        System.out.println(Arrays.toString(res2));

    }
}
